1. Field of the Invention
The invention relates generally to the field of data processing, and more particularly to methods and apparatus for managing cache memory resources in a data processing system. A Write/Load cache protocol is described which may be used for maintaining cache coherency and performing barrier synchronization in multiprocessor computer systems, and for cooperating with prefetch mechanisms to allow data to be loaded into a central processor unit's (CPU) cache (in both single and multiprocessor systems) in anticipation of future memory references.
The new protocol is defined such that when a cache observes a Write/Load command (and associated data item) on a bus to which the cache is attached, the cache is accessed and (a) if the data item is in the cache, the new value of the data item from the bus is copied into and replaces the data item in cache; and (b) if the data item is not in the cache, a new data item is created therein (preferably using the normal cache replacement policy), and the value of the data item on the bus is loaded into the cache. Thus, a protocol is provided which allows cache to be loaded via an external entity, i.e., an entity other than the processor being directly serviced by the cache.
2. Description of the Related Art
Two major protocols are well known for maintaining coherence across multiple caches. These protocols are:
(1) Write/Invalidate, which invalidates entries in all other caches when a data item in a local cache is rewritten; and PA1 (2) Write/Update, which updates copies of a data item in remote caches when a data item in a local cache is rewritten.
For both of these protocols, a remote cache is changed only when the remote cache contains a copy of an entry in a local cache that is rewritten. If a remote cache does not contain a copy of the locally rewritten item, then the remote cache is not changed.
These basic protocols (and variations thereof) are typically used to achieve cache coherence in multiprocessor computer architectures. They are well known to those skilled in the art, and are well documented in published technical documents and articles.
In particular, an article by J. R. Goodman entitled "Using Cache Memory To Reduce Processor/Memory Traffic" appearing at pp. 124-131 of the proceedings of the 10th Annual Computer Architecture Symposium, published in June, 1983, teaches an early cache coherence protocol called "Write Once". The Write Once protocol is a model for the Write/Invalidate protocol.
L. Rudolph and Z. Segall, in an article entitled "Dynamic Decentralized Cache Schemes For MIMD Parallel Processors" published in 1984, at pp. 340-347 in the 11th Annual International Symposium on Computer Architecture, formally described both the Write/Update and Write/Invalidate protocols. However, no mechanism is described for entering data into a remote cache unless it is done by updating values of data that are already held by the cache.
A very general cache coherence technique that attempts to embody all reasonable variations of the cache coherence protocols known in 1986, is described in an article by P. Sweazey and A. J. Smith, entitled "A Class of Compatible Cache-Consistency Protocols and Their Support By the IEEE Futurebus", published in June, 1986, at pp. 414-423 in the proceedings of the 13th Annual International Symposium on Computer Architecture. The implementation of the cache coherency technique taught in the article includes both Write/Update and Write/Invalidate protocols with several minor variations. The technique described, like the protocols described in the other articles referenced hereinbefore, does not permit data to be entered into a cache by an external process unless the cache data altered are updated copies of data held externally.
Karlin et al, in an article entitled "Competitive Snoopy Caching" published in Vol. 3, pp. 79-119 of Algorithmica, in 1988, also describe a class of cache coherency protocols intended to be representative of all reasonable protocols. Again, several variations of the Write/Update and Write/Invalidate protocols are described. No protocol variation is described that permits cache data to be altered by an external process, except by updating exiting data that are also held externally.
J. R. Goodman and P. J. Woest, in an article entitled "The Wisconsin Multicube: A New Large-Scale Cache-Coherent Multiprocessor", published at pp. 422-431 in the proceedings of the 15th Annual International Symposium on Computer Architecture, in May, 1988, describe a novel two-dimentional arrangement of processors and buses. The processors each have caches that are maintained as a coherent collection of caches through an extension of cache coherence protocols. According to the teachings of Goodman et al, when a processor alters an item, it obtains control of a column bus, and broadcasts a coherence control signal. All caches on that column receive this information and rebroadcast the information on their respective rows. In this way, all caches in the system receive coherence information in two cycles.
According to this scheme, the caches in a column that receive broadcast information alter their control tables, whether or not they contain a copy of the datum that was altered. The reason for altering their states is that they need to hold this information in order to rebroadcast it in the next available cycle for their respective row buses. The protocol used for the second cycle is Write/Invalidate of Write/Update, or a variant thereof.
Once again, no provision is made for altering a cache during the second cycle unless the cache has a copy of the datum originally altered.
Changes made to the caches on a particular column during the first cycle are for the purpose of broadcast during the second cycle. Goodman et al do not teach using such changes for honoring future memory references, and treat cache contents as being distinct from the information held for second cycle broadcast.
In an article by J. S. Eggers and R. H. Katz, entitled "Evaluating the Performance of Four Snooping Cache Coherency Protocols", published at pp. 2-15 in the proceedings of the 16th Annual International Symposium on Computer Architecture, in June, 1989, it was recognized that the existing Write/Update and Write/Invalidate protocols might perform less effectively than a new protocol, a slightly more powerful version of Write/Update as described in the article. The Eggers and Katz protocol updates an item when it is held in a remote cache either as a valid item or as an invalid item that has not yet been purged from the cache. Hence, their variation of Write/Update can revalidate an item in a remote cache, whereas the original variation of Write/Update would leave the item invalid. However, Eggers and Katz do not provide a means for forcing an item into a remote cache if the item were not already held there in some form.
As can be seen with reference to the publications described hereinabove, although the prior art has sought to examine all reasonable variations of cache coherency protocols, no protocol is taught which permits forcing data into a remote cache. As will be seen with reference to the detailed description set forth hereinafter, such a protocol, defined herein as a Write/Load protocol, may be used (1) for maintaining cache coherency and performing barrier synchronization in multiprocessor computer systems and (2) for cooperating with prefetch mechanisms to allow data to be loaded into a central processor unit's (CPU) cache (in both single and multiprocessor systems) in anticipation of future memory references.
Accordingly, it would be desirable if methods and apparatus for supporting a Write/Load Cache Protocol, and, for executing Write/Load commands based on such protocol, were provided. In particular, it would be desirable if the protocol was operative, whenever a cache observes a Write/Load command (and associated data item) on a bus to which the cache is attached, to cause the cache to be accessed and (a) if the data item is in the cache, cause the new value of the data item from the bus to be copied into and replace the data item in cache; and (b) if the data item is not in the cache, to cause a new data item to be created therein (preferably using the normal cache replacement policy), and the value of the data item on the bus to be loaded into the cache. Such a protocol would allow cache memory to be loaded via an external entity, i.e., an entity other than the processor being directly serviced by the cache.